class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            //背包问题求解的是有限组合问题
            //此题并非组合问题，而是排列问题，不能用背包问题解决
            //找出重复子问题，抽象出状态表示
            int n = nums.size();
            vector<uint64_t> dp(target+1);
            //dp[i] 表示要凑到和为i 有多少种排列方法
            dp[0] = 1;
            for(int i = 1 ; i < target+1 ;i++){
                for(auto x: nums){
                    if(i>=x) dp[i]+= dp[i-x];
                }
            }
            return dp[target];
        }
    };